package com.ljx.Dynamic;

/**
 * @author 李加喜
 * @Package com.ljx.Dynamic
 * @date 2021-11-02 23:35
 */

import java.util.Arrays;

/**
 * 322 零钱兑换
 */
public class Two {
    public static void main(String[] args) {
        Two two = new Two();
        int[] coins={1,2,5};
        int amount=11;
        System.out.println(two.coinChange(coins,amount));
    }
    public int coinChange(int[] coins, int amount) {
        int[] me=new int[amount+1];
        Arrays.fill(me,-66);
        return dp(me,coins,amount);
    }
    public int dp(int[] me,int[] coins, int amount){
        if (amount==0) {
            return 0;
        }
        if (amount<0){
            return -1;
        }
        if (me[amount]!=-66){
            return me[amount];
        }
        int min=Integer.MAX_VALUE;
        for (int coin:coins){
            // 计算选择当前硬币之后的剩余的最小值
            int subMin=dp(me,coins,amount-coin);
            if (subMin==-1){
                // 无解
                continue;
            }
            // +1表示加上当前选择的这个硬币
            min=Math.min(min,subMin+1);
        }
        me[amount]=min==Integer.MAX_VALUE?-1:min;
        return min==Integer.MAX_VALUE?-1:min;
    }
    // 也可以使用dp数组
    public int dp2(int[] coins, int amount){
        int[] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        // 设置base case
        dp[0]=0;
        //循环在遍历所有状态的所有取值
        for (int i=0;i<dp.length;i++){
            //内层循环找最小值
            for (int coin:coins){
                if (i-coin<0){
                    continue;
                }
                dp[i]=Math.min(dp[i],dp[i-coin]);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}
